Menger's theorem

In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927. The edge-connectivity version of Menger's theorem was later generalized by the max-flow min-cut theorem.

The edge-connectivity version of Menger's theorem is as follows:

Let G be a finite undirected graph and x and y two distinct vertices. Then the theorem states that the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.

Extended to subgraphs: a maximal subgraph disconnected by no less than a k-edge cut is identical to a maximal subgraph with a minimum number k of edge-independent paths between any x, y pairs of nodes in the subgraph.

The vertex-connectivity statement of Menger's theorem is as follows:

Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal disconnects x and y) is equal to the maximum number of pairwise vertex-independent paths from x to y.

Extended to subgraphs: a maximal subgraph disconnected by no less than a k-vertex cut is identical to a maximal subgraph with a minimum number k of vertex-independent paths between any x, y pairs of nodes in the subgraph.

Menger's theorem holds for infinite graphs, and in that context it applies to the minimum cut between any two elements that are either vertices or ends of the graph (Halin 1974). The following statement is equivalent to Menger's theorem for finite graphs and is a deep recent result of Ron Aharoni and Eli Berger for infinite graphs (originally a conjecture proposed by Paul Erdős): Let A and B be sets of vertices in a (possibly infinite) digraph G. Then there exists a family P of disjoint A-B-paths and a separating set which consists of exactly one vertex from each path in P.

References

Menger, Karl (1927). "Zur allgemeinen Kurventheorie". Fund. Math. 10: 96–115.
Aharoni, Ron and Berger, Eli (2009). "Menger's Theorem for infinite graphs". Inventiones Mathematicae 176: 1–62. doi:10.1007/s00222-008-0157-3. http://www.springerlink.com/content/267k231365284lr6/?p=ddccdd0319b24e53958e286488757ca7&pi=0.
Halin, R. (1974), "A note on Menger's theorem for infinite locally finite graphs", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 40: 111–114, MR 0335355 .

Menger's theorem

References

External links